# Generator for Turmite rules: but only for the case when there is a single
# Turmite in the world; collisions aren't handled correctly. This is for speed
# of generation, which is otherwise very slow.
#
# Following work of Ed Pegg Jr.
# specifically the Mathematica notebook linked-to from here:
# http://www.mathpuzzle.com/26Mar03.html
#
# contact: tim.hutton@gmail.com

import golly
import random
import string

# dirs=['N','E','S','W']
opposite_dirs=[2,3,0,1] # index of opposite direction

# what direction would a turmite have been facing to end up here from direction
# d if it turned t: would_have_been_facing[t][d]
would_have_been_facing={ 
1:[2,3,0,1], # no turn
2:[1,2,3,0], # right
4:[0,1,2,3], # u-turn
8:[3,0,1,2], # left
}

prefix = 'Turmite' 

example_spec = "{{{1, 8, 1}, {1, 8, 1}}, {{1, 2, 1}, {0, 1, 0}}}"

# DEBUG: generate a random rule
# TODO: need a better way of avoiding the dull rules while not missing any goodness
# e.g. if all state or color becomes unreachable then rule is bad (hard to test for?)
# e.g. (simpler) if turmite gets stuck in a state then rule is bad
# e.g. if transitions never change the color of a cell then rule is bad
# e.g. if turmite can get stuck in period-2 cycles then rule is bad (or might it avoid them?)
# e.g. (simpler) if turmite has (c,4,s) for any state s and color c then will wobble on the spot
# e.g. if turmite will zip off: if on color 0 with state s the turmite does (?,1,s) then rule is bad
import random
ns = 2
nc = 2
while True: # (we break out if ok)
    example_spec = '{'
    for state in range(ns):
        if state > 0:
            example_spec += ','
        example_spec += '{'
        for color in range(nc):
            if color > 0:
                example_spec += ','
            new_state = random.randint(0,ns-1)
            new_color = random.randint(0,nc-1)
            dir_to_turn = [1,2,4,8][random.randint(0,3)]
            example_spec += '{' + str(new_color) + "," + str(dir_to_turn) + "," + str(new_state) + '}'
        example_spec += '}'
    example_spec += '}'
    # is rule acceptable?
    is_rule_acceptable = True
    action_table = eval(string.replace(string.replace(example_spec,'}',']'),'{','['))
    # will turmite zip off? if on color 0 with state s the turmite does (?,1,s) then rule is bad
    for state in range(ns):
        if action_table[state][0][1]==1 and action_table[state][0][2]==state:
            is_rule_acceptable = False
    # does Turmite change at least one color?
    changes_one = False
    for state in range(ns):
        for color in range(nc):
            if not action_table[state][color][0] == color:
                changes_one = True
    if not changes_one:
        is_rule_acceptable = False
    # does turmite get stuck in any state?
    for state in range(ns):
        changes_state = False
        for color in range(nc):
            if not action_table[state][color][2] == state:
                changes_state = True
        if not changes_state:
            is_rule_acceptable = False
    # does turmite wobble on the spot?
    for state in range(ns):
        for color in range(nc):
            if action_table[state][color][0]==color and action_table[state][color][1]==4 and action_table[state][color][2]==state:
                is_rule_acceptable = False
    if is_rule_acceptable:
        break
            
spec = golly.getstring(
'''This script will create a Turmite CA for a given specification.

Enter a specification string: a curly-bracketed table of n_states rows
and n_colors columns, where each entry is a triple of integers. 
The elements of each triple are:
a: the new color of the square
b: the direction(s) for the Turmite to turn (1=noturn, 2=right, 4=u-turn, 8=left)
c: the new internal state of the Turmite

Example:
{{{1, 2, 0}, {0, 8, 0}}}
(example pattern #1)
Has 1 state and 2 colors. The triple {1,2,0} says: 
1. set the color of the square to 1
2. turn right (2)
3. adopt state 0 (no change) and move forward one square
This is Langton's Ant.

(Collisions aren't properly dealt with by the rule table generated by this 
script. If you're interested in colliding multiple turmites, find the 
Turmites.zip on the Rule Table Repository.)

Enter string:
(default is a random example)''', example_spec, 'Enter Turmite specification:')

# convert the specification string into action_table[state][color]
# (convert Mathematica code to Python and run eval)
action_table = eval(string.replace(string.replace(spec,'}',']'),'{','['))
n_states = len(action_table)
n_colors = len(action_table[0])
# (N.B. The terminology 'state' here refers to the internal state of the finite
#       state machine that each Turmite is using, not the contents of each Golly
#       cell. We use the term 'color' to denote the symbol on the 2D 'tape'. The
#       actual 'Golly state' in this emulation of Turmites is given by the 
#       "encoding" section below.)

# TODO: check table is full and valid

total_states = n_colors+n_colors*n_states*4

# problem if we try to export more than 255 states
if total_states > 255:
    golly.warn("Number of states required exceeds Golly's limit of 255.")
    golly.exit()

# encoding: 
# (0-n_colors: empty square)
def encode(c,s,d):
    # turmite on color c in state s facing direction d
    return n_colors + 4*(n_states*c+s) + d

# http://rightfootin.blogspot.com/2006/09/more-on-python-flatten.html
def flatten(l, ltypes=(list, tuple)):
    ltype = type(l)
    l = list(l)
    i = 0
    while i < len(l):
        while isinstance(l[i], ltypes):
            if not l[i]:
                l.pop(i)
                i -= 1
                break
            else:
                l[i:i + 1] = l[i]
        i += 1
    return ltype(l)
    
# convert the string to a form we can embed in a filename
spec_string = ''.join(map(str,map(lambda x:hex(x)[2:],flatten(action_table)))) 
# (ambiguous but we have to try something)

f=open(golly.getdir('rules')+prefix+'-'+spec_string+'.table', 'w')
f.write("# Turmite: "+spec+"\n\n")
f.write("n_states:"+str(total_states)+"\n")
f.write("neighborhood:vonNeumann\n")
f.write("symmetries:none\n\n")
for i in range(5):
    f.write("var a"+str(i)+"={"+','.join(map(str,range(n_colors)))+"}\n") # 0,n_colors-1 : no turmite present
f.write("\n# Turmite leaving this square:\n")
for output_color in range(n_colors):
    n_printed=0
    for state in range(n_states):
        for color in range(n_colors):
            if action_table[state][color][0]==output_color:
                for d in range(4):
                    if n_printed==0:
                        f.write("var b"+str(output_color)+"={")
                    else:
                        f.write(",")
                    f.write(str(encode(color,state,d)))
                    n_printed+=1
    if n_printed>0:
        f.write("}\nb"+str(output_color)+",a0,a1,a2,a3,"+str(output_color)+"\n")
f.write("\n# Turmite entering this square:\n")
for state in range(n_states):
    for color in range(n_colors):
        # what direction does the turmite turn?
        turn = action_table[state][color][1]
        if turn==0:
            continue # turmite halts
        new_state = action_table[state][color][2]
        for d in range(4):
            # what direction would the turmite have to be facing to end up here?
            facing = would_have_been_facing[turn][d]
            for central_color in range(n_colors):
                # output the required transition
                f.write(str(central_color))
                for element in range(4):
                    if element==d:
                        f.write(","+str(encode(color,state,facing)))
                    else:
                        f.write(",a"+str(element))
                f.write(","+str(encode(central_color,new_state,opposite_dirs[d]))+"\n")
            
f.flush()  # ensure file is complete (only on Windows?)
f.close()

# now we can switch to the new rule
golly.setalgo("RuleTable")   # in case name.tree exists
golly.setrule(prefix+'-'+spec_string)
golly.new(prefix+'-demo.rle')

golly.setcell(0,0,n_colors)
golly.fit()
golly.show('Created '+prefix+'-'+spec_string+'.table, and selected this rule.')









